"Halftoning" is the process of constructing a binary image, i.e. a bi-level image, from a gray scale image, i.e. a multi-level image. The constructed binary image can then be displayed by means of binary devices, such as newspaper printers and laser printers. An n-bit gray scale image is converted into an one-bit binary image perceived to contain a continuous tone. The gray scale image may be passed through a sequence of operators that assign pixel values of 1 or 0 for each pixel of the resulting binary image.
"Inverse halftoning" is the process of reconverting the binary image into an approximation of the original gray scale image. Inverse halftoning can be applied to a wide variety of binary image processing problems, such as scaling, tone correction, interchanging between halftone methods, facsimile image processing, and image compression. For example, a gray scale image may be constructed from a binary image, whereafter the gray scale image undergoes a processing operation and is finally rehalftoned.
A binary image is a two-dimensional array of pixels having pixel values limited to two levels. On the other hand, a gray scale image is a two-dimensional light intensity function x(i,j), where i and j denote discrete pixel coordinates and where the pixel value at any pixel x is proportional to the gray level of the image at that point. For example, the gray scale image may be an eight-bit scale having 256 possible gray levels.
Halftoning methods that use algorithms can generally be classified into two different categories--ordered dither and error diffusion. Ordered dither can be described at a basic level as a procedure of converting the gray scale image by thresholding the gray input with a periodically repeated threshold matrix. Error diffusion can be described as "spreading out" the error between an input gray-scale pixel and its binary output over a small area of the binary image. A weighted combination of output errors from previously processed pixels with respect to the scanning strategy is added to the input pixel, and the sum is thresholded to produce the binary output. Thus, error diffusion provides a local average within any small area of the binary image to approximate the gray level in the corresponding area of the gray scale image.
The two types of halftoning produce binary images that are substantially different both with respect to structure and characteristics, e.g., the frequency spectra. Consequently, inverse halftoning methods designed for converting one type of halftone image generally do not work well for converting the other type. With regard to inverse halftoning of dithered images, one technique is to use a "neighborhood approach" using adaptive run-lengths of 1's and 0's (ABRL). This performs particularly well in a three-level cascade algorithm comprised of ABRL, statistical smoothing, and impulse removal Miceli et al , "Inverse Halftoning," Journal of Electronic Imaging, column, vol. 1, pages 143-151, April 1992.
With respect to inverse halftoning of error diffused images, the use of look-up tables has recently been suggested. Ting et al., "Error Diffused Image Compression Using a Halftone-to-Gray Scale Decoder and Predictive Pruned Tree-Structured Vector Quantization," submitted to IEEE Transactions on Image Processing, 1992. Ting et al. describe using a small window which is slid over the error diffused image. The content of the binary pixels in the window serves as an address to a look-up table. A gray level value is then retrieved as the constructed gray level of the center pixel in the window. Thus, the inverse halftoning procedure can be interpreted as a decoding operation, where the "decoder" is the look-up table that associates a particular gray level with a particular bit pattern. The look-up table is constructed by a training algorithm using a collection of test images in the same manner as designing vector quantizers. While this method of inverse halftoning of an error diffused image works reasonably well, the training of the look-up table is time consuming. Moreover, because error diffusion produces a binary image in which the local average within any small area of the image approximates the gray level of the corresponding small area of the original gray scale image, one can obtain very different bit patterns corresponding to the same local gray level by simply shifting a halftoning window a small amount in any direction. The different bit patterns will result in different addressing to the look-up table during inverse halftoning. On the other hand, one can generate very different binary images from the same gray scale image by merely changing the initial condition in the error diffusion process. This means that the correlation between a specific bit pattern with the original local gray level is not very high, and hence the performance of the look-up table approach is limited.
Low pass filtering is the conventional way of reconstructing gray scale images from binary images. However, while the error diffusion process can be interpreted as one that injects noise into the gray scale image primarily at the high frequency range, there are several reasons why low pass filtering alone does not produce inverse halftoned images of sufficient quality. Firstly, low pass filtering cannot remove all of the noise (i.e. error) purposefully introduced by the error diffusion process, since there are noise components at the low frequency range. Secondly, there may have been high frequency components in the original gray scale image, so that removal of noise at the high frequency range will also remove these desirable high frequency components. Low pass filters are not so selective as to unambiguously determine whether a high frequency component originated from the gray scale image or from the error diffusion process. An example of low pass filtering is one which uses a filter at one-half of the maximum possible bandwidth of the digital image, i.e., the cut-off frequency is at f.sub.s /4, where f.sub.s is the sampling frequency. A significant amount of residue noise resulting from the error diffusion process will still remain at the output image. The residue noise cannot be removed by further low pass filtering unless the cut-off frequency of the filter is lowered significantly. However, lowering the cut-off frequency further would result in the removal of desired components, thereby generating an overly blurred image.
It is an object of the present invention to provide a method and apparatus for converting a binary image into a high quality gray scale image.